/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.matching;

import java.util.Arrays;

public class SundayMatcher {

	public static int comparisons = -1;
	
	public static int[] computeShiftTable(int alphabetSize, int[] pattern) {
		int[] shift = new int[alphabetSize];
		Arrays.fill(shift, pattern.length+1);
		for (int i=0; i<pattern.length; ++i) {
			shift[pattern[i]]=pattern.length-i;
		}
		return shift;
	}
	
	/** Right-to-left variant. */
	public static int findMatches(int alphabetSize, int[] text, int[] pattern) {
		int[] shift = computeShiftTable(alphabetSize, pattern);
		int comparisons = 0;
		int count = 0;
		// position of last character in current window
		int n = pattern.length-1;
		while (n<text.length) {
			int i = 0;
			while (i<pattern.length) {
				comparisons+=1;
				if (text[n-i]!=pattern[pattern.length-i-1]) break;
				i+=1;
			}
			if (i==pattern.length) {
				count+=1;
			}
			if (n==text.length-1) break;
			// does this one really count?
			comparisons+=1;
			n+=shift[text[n+1]];
		}
		// Log.println(Log.Level.DEBUG, "Sunday: Comparisons: "+comparisons);
		SundayMatcher.comparisons = comparisons;
		return count;
	}
	
}
